class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1)
            return nums[0];
        return max(best(nums, 1, n - 1), best(nums, 2, n - 2) + nums[0]);
    }

    int best(vector<int>& nums, int l, int r)
    {
        if (l > r)
            return 0;
        if (l == r)
            return nums[l];
        if (l + 1 == r)
            return max(nums[l], nums[r]);

        int prepre = nums[l];
        int pre = max(nums[l], nums[l + 1]);
        int cur;
        for (int i = l + 2; i <= r; i++)
        {
            cur = max(pre, nums[i] + prepre);
            prepre = pre;
            pre = cur;
        }
        return cur;
    }
};